利用软件方法利用 ILP II
AP SHANTHI博士
本模块的目标是讨论更多用于开发 ILP 的软件方法。详细讨论了软件流水线、预测和软件流水线的概念。
自大约 1985 年以来，所有处理器都使用流水线来重叠指令的执行并提高处理器的性能。指令之间的这种重叠称为指令级并行性，因为可以并行评估指令。有两种可分离的技术来利用 ILP：
动态并依赖于硬件来定位并行性
静态且更多地依赖软件
编译器采用静态技术来提高性能。主要使用硬件方法的处理器在这些优化之上使用其他技术来提高性能。动态的、硬件密集型方法主导了 PIII、P4 等处理器，甚至是 i3、i5 和 i7 等最新处理器。软件密集型方法用于像安腾这样的处理器。前面的模块专注于通过循环展开来利用循环级并行性。本模块将讨论可用于利用 ILP 的其他技术。
软件流水线： 这是另一个可以提高循环执行性能的优化。这是一个象征性的展开过程。它通过使用来自同一循环的不同迭代的指令填充循环体每次迭代中的延迟来获得其性能增益。通过将来自不同迭代的指令调度到循环的单个迭代中，形成具有独立指令的新循环。这些独立的指令构成了循环的内核，可以并行执行。通过从不同的迭代中选择指令，整个循环体将相关计算彼此分开，从而增加了可以无停顿地调度展开循环的可能性。由于我们从多次迭代中挑选指令并形成一个内核，一些来自初始迭代和最终迭代的指令将不包括在内。这些将作为启动代码和结束代码单独处理。
借助示例可以最好地解释软件流水线的概念。考虑用于循环展开并在此处重复的相同示例，以方便使用。考虑以下迭代循环和等效的程序集。
for(i=1;i<=1000;i++)
x(i) = x(i) + s;
Loop: LD F0,0(R1) ;F0=向量元素
ADDD F4,F0,F2 ;从 F2 添加标量
SD 0(R1),F4 ;存储结果
SUBI R1,R1,8 ;指针递减8bytes (DW)
BNEZ R1,Loop ;branch R1!=0
NOP ;延迟分支槽
循环体由三个指令组成，每个指令都相互依赖。循环中的真实数据依赖性如下所示。另外两条指令称为循环维护代码。
Loop: LD F0,0(R1) ;F0=向量元素
ADDD F4,F0,F2 ;在F2中添加标量
SD 0(R1),F4 ;存储结果
SUBI R1,R1,8 ;递减指针8B (DW)
BNEZ R1,Loop ;branch R1!=0
NOP ;延迟分支槽
出于讨论的目的，让我们考虑以下一组延迟：
指令产生结果 使用结果说明 时钟周期的延迟
FP ALU 操作 另一个 FP 操作 3
FP ALU 操作 存储双 2
加载双倍 FP ALU 操作 1
加载双倍 存储双 0
整数运算 整数运算 0
原始调度：如果我们尝试为上述延迟调度代码，调度可以如下所示。第一条和第二条从属指令之间有一个停顿，Add 和从属 Store 之间有两个停顿。在循环维护代码中，由于 Sub 和 Branch 之间的数据依赖关系，也需要引入一个档位。最后一个停顿用于分支指令，即分支延迟槽。循环的一次迭代需要十个时钟周期来执行。
1 循环：LD F0, 0(R1) ;F0=向量元素
2档
3 ADDD F4, F0, F2 ;在F2中添加标量
4档
5档
6 SD 0(R1), F4 ;存储结果
7 SUBI R1, R1, 8 ;递减指针 8 字节 (DW)
8档
9 BNEZ R1, Loop ;branch R1!=0
10stall ;延迟分支槽
每个停顿都可以视为无操作（nop）。我们可以通过插入来自不同迭代的指令来替换 nops 来执行有用的操作，这正是软件流水线所做的。
软件流水线的步骤：软件流水线需要遵循三个步骤。
展开循环体，展开因子为 n
– 假设值为 3，展开的循环如下所示：
LD F0,0(R1)
添加 F4,F0,F2
SD 0(R1),F4
LD F6,-8(R1)
添加 F8,F6,F2
SD -8(R1),F8
LD F10,-16(R1)
添加 F12,F10,F2
SD -16(R1),F12
– 由于循环已展开，因此未包含循环维护代码。
– 三个迭代将被“折叠”成一个包含来自原始循环体不同迭代的指令的循环体
选择要在流水线循环中遵循的顺序
– 每条指令（LD、ADD.D 和 SD）必须至少选择一次，以确保在将循环折叠为单个流水线循环时不会遗漏任何指令
– 第 (i+2) 个的 LD。迭代，从第 (i+1) 次开始添加。迭代和来自迭代 I 的 LD 被选择来形成内核
将来自不同迭代的指令粘贴到新的流水线循环体中
– 软件流水线循环在不展开循环的情况下交错来自不同迭代的指令，如下图所示。这种技术是 Tomasulo 算法在硬件中所做的软件对应物。
还有一些在循环开始之前需要的启动代码以及在循环完成后完成的代码。通过查看展开的版本，我们可以看到启动代码和完成代码需要是什么。对于启动，我们将需要执行与迭代 1 和 2 相对应的任何不会被执行的指令。这些指令是迭代 1 和 2 的 LD 和迭代 1 的 ADD.D。对于结束代码，我们需要执行在最后两次迭代中不会执行的任何指令。这些包括最后一次迭代的 ADD.D 和最后两次迭代的 SD。启动代码称为 prolog、preamble 或 preheader。结束代码称为尾声、后同步码或后头。请注意，该过程类似于硬件管道被填满。管道需要一些时间来填满，然后管道在所有阶段都已满的情况下工作，然后管道需要一些时间来排空。正是由于这种相似性，它被称为软件流水线。当内核运行时，我们有一组完全独立的指令，可以在 VLIW 等多问题处理器上进行调度，以获得最大性能。
这个循环可以以每个结果 5 个周期的速率运行，忽略启动和清理部分，并假设 DADDUI 被安排在 ADD.D 之后，并且 LD 指令，具有调整的偏移量，被放置在分支延迟槽。因为加载和存储被 16 的偏移量分隔（两次迭代），循环应该少运行两次迭代。请注意，寄存器（例如，F4、F0 和 R1）的重用需要硬件来避免循环中可能发生的 WAR 危险。在这种情况下，这种危险应该不是问题，因为不应该发生与数据相关的停顿。
The major advantage of software pipelining over loop unrolling is that software pipelining consumes less code space. Each of them reduce a different type of overhead. Loop unrolling reduces the overhead of the loop—the branch and counter-update code. Software pipelining reduces the time when the loop is not running at peak speed to once per loop at the beginning and end. If we unroll a loop that does 100 iterations a constant number of times, say 5, we pay the overhead 100/5 = 20 times – every time the inner unrolled loop is initiated. Because these techniques attack two different types of overhead, the best performance can come from doing both. The difference between the two techniques is illustrated in Figure 21.1.
预测：到目前为止，我们已经研究了编译器用来利用 ILP 的不同技术。当代码在编译时可预测时，ILP 的软件支持是最好的。但如果没有可预测性呢？在这种情况下，编译器无法自行利用 ILP，而是依赖于硬件提供一些支持。我们现在来看看这些技术。首先，我们将讨论预测。
处理器的 ISA 中提供了谓词或条件指令，编译器使用这些指令。如果条件为真，则执行断言指令，如果条件为假，则取消断言指令。因此，可以移除分支并且可以将测试分支的条件合并为指令中的谓词。因此，控制相关性被转换为数据相关性。一些架构有几个谓词指令，而一些架构支持全谓词。也就是说，所有指令的执行都由一个谓词控制。此功能允许我们简单地转换依赖于分支的大代码块。当我们有一个 if then else 构造时，if 部分中的语句将替换为谓词，else 子句中的所有语句都将替换为相反的谓词，例如零和非零。这个过程叫做如果转换。
谓词指令还可用于推测性地移动对时间要求严格的指令，但如果在保护分支之前移动，则可能会导致异常。考虑图 21.2 中所示的以下代码序列，它是一个两发出超标量，它可以在每个周期发出一个内存引用和一个 ALU 操作的组合，或者一个单独的分支。第二个周期浪费了一个槽，最后一个 LW 指令对前一个 LW 有数据依赖。如果不采取分支，这将导致停顿。
使用谓词指令可以改进调度，如图 21.3 所示。条件加载指令 LWC 有助于在第二个时钟周期填充槽，并避免由于最后一条指令的数据依赖性而导致的停顿。除非第三个操作数为零，否则将执行条件加载。因此，这提供了更好的时间表。
谓词指令有一些缺点。他们是：
取消的谓词指令也会占用一些处理器资源
当可以及早评估谓词时，谓词指令更有用
当控制流涉及的不仅仅是一个简单的替代序列时，条件指令的使用可能会受到限制
与无条件指令相比，条件指令可能会有一些速度损失
由于数据相关性通常在管道早期解决，这可能会导致停顿
具有硬件支持的软件推测：编译器使用静态预测从程序结构或使用配置文件来预测编译时分支的行为。在这种情况下，编译器可能想推测是改进调度还是提高发布率。谓词指令提供了一种推测方法，但当控制依赖可以通过 if 转换完全消除时，它们确实更有用。但是，在很多情况下，我们不仅希望在分支之前移动推测指令，而且还希望在条件评估之前移动推测指令，而预测无法实现这一点。
为了进行激进的投机，我们需要三个能力：
编译器找到指令的能力，在可能使用寄存器重命名的情况下，可以推测性地移动而不影响程序数据流
能够忽略推测指令中的异常，直到我们知道此类异常确实应该发生，并且
推测性地交换加载和存储，或存储和存储的能力，这可能有地址冲突。
其中第一个是编译器功能，而后两个需要硬件支持，我们接下来将进行探讨。
保留异常行为的硬件支持：为了雄心勃勃地进行推测，我们必须能够移动任何类型的指令并仍然保留其异常行为。能够做到这一点的关键是观察到一个被错误预测的推测序列的结果不会在最终计算中使用，并且这样的推测指令不应该导致异常。
已经研究了四种方法来支持更雄心勃勃的推测而不引入错误的异常行为：
硬件和操作系统协同忽略推测性指令的异常。这种方法为正确的程序保留了异常行为，但不为不正确的程序保留了异常行为。
使用从不引发异常的推测性指令，并引入检查以确定何时应该发生异常。
当指令导致异常时，一组状态位，称为毒位，附加到由推测指令写入的结果寄存器。当正常指令尝试使用该寄存器时，有毒位会导致故障。
提供一种机制来指示指令是推测性的，并且硬件缓冲指令结果，直到确定该指令不再是推测性的。
最后，可以进行软件和硬件推测之间的比较。下面提供了比较。
在软件推测的情况下，必须消除内存引用的歧义
当控制流不可预测时，基于硬件的推测效果更好
即使对于推测指令，基于硬件的推测也能保持完全精确的异常模型
与软件推测机制不同，基于硬件的推测不需要补偿或簿记代码
基于编译器的方法可能受益于在代码序列中看得更远的能力，从而导致比纯硬件驱动的方法更好的代码调度
具有动态调度的基于硬件的推测不需要不同的代码序列来为架构的不同实现实现良好的性能
总而言之，我们已经研究了如何实现软件流水线。它执行一个象征性的展开过程，就像 Tomasulo 在硬件中所做的那样。我们还研究了编译器如何使用谓词或条件指令来利用更多 ILP。如果硬件支持保留异常行为和内存消歧，编译器也可以使用推测的概念来发现更多 ILP。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A. Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。